#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include"stack.h"

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void Print(int* p, int size)
{
	for (int i = 0; i < size; i++) {
		printf("%d ", p[i]);
	}
	printf("\n");
}


int QuickSort1(int* p, int begin, int end)
{
	int lefti = begin;
	int righti = end;
	int keyi = begin;
	while (lefti < righti)
	{
		while (lefti < righti && p[righti] >= p[keyi])
		{
			righti--;
		}
		while (lefti < righti && p[lefti] <= p[keyi])
		{
			lefti++;
		}
		Swap(&p[lefti], &p[righti]);
	}
	Swap(&p[lefti], &p[keyi]);
	return  lefti;
}

void QuickSortNonRecursion(int* p, int begin, int end)
{
	stack st;
	StInit(&st);
	StPush(&st, begin);
	StPush(&st, end);
	while (JudgeEmpty(&st))
	{
		int right = GetTop(&st);
		StPop(&st);
		int left = GetTop(&st);
		StPop(&st);
		int mid = QuickSort1(p, left, right);


		if ((right - (mid + 1)) > 0) {
			StPush(&st, mid + 1);
			StPush(&st, right);
		}

		if (((mid - 1) - left )> 0) {
			StPush(&st, left);
			StPush(&st, mid - 1);
		}
	}
	//StDestroy(&st);
}
void test()
{
	int arr[] = { 5,4,3,8,-2,9,1,4,3,6,-5 };
	int size = sizeof(arr) / sizeof(int);
	QuickSortNonRecursion(arr, 0, size - 1);
	Print(arr, size);

}
int main()
{
	test();
	return 0;
}
